|
In graph theory and theoretical computer science, the level ancestor problem is the problem of preprocessing a given rooted tree ''T'' into a data structure that can determine the ancestor of a given node at a given distance from the root of the tree. More precisely, let ''T'' be a rooted tree with ''n'' nodes, and let ''v'' be an arbitrary node of ''T''. The level ancestor query LA(''v'',''d'') requests the ancestor of node ''v'' at depth ''d'', where the depth of a node ''v'' in a tree is the number of edges on the shortest path from the root of the tree to node ''v''. It is possible to solve this problem in constant time per query, after a preprocessing algorithm that takes O(''n'') and that builds a data structure that uses O(''n'') storage space. ==Naive methods== The simplest way to find a level ancestor of a node is to climb up the tree towards the root of the tree. On the path to the root of the tree, every ancestor of a node can be visited and therefore reported. In this case, the tree does not need to be preprocessed and the time to answer a query is O(''h''), where "h" is the height of the tree. This approach is not feasible in situations where the tree may have large height and a large number of a queries are required to be processed. Alternatively, all the possible solutions can be precomputed and stored in a table. In this case, the queries can be answered in O(1) but the space and the preprocessing time is O(''n''2). The simplest queries that can be answered in constant time without any preprocessing are LA(''v'', 0) and LA(''v'', depth(''v'')). In the former case, the answer is always the root of the tree and in the latter case, the answer is the node ''v'' itself. Each of these results takes O(1). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Level ancestor problem」の詳細全文を読む スポンサード リンク
|